%--------------------------------------------------------------------------------%
%    This program is used to cluster a data with K-Medoids (PAM) algorithm       %
%                                                                                %   
%    Three parameters:                                                           %
%         dist_matrix -  distance matrix of the dataset needs to be clustered;   %
%                   k -  number of clusters                                      %
%       num_iteration -  the stop criterion (e.g. 200 or 400)                    %
%                                                                                %   
%    Three return values:                                                        %
%               group -  each group stands for a cluster                         %
%               label -  label for each object in the dataset                    %
%              medoid -  the centers of clusters                                 %                                                                                %
%     Implemented by:  Qiang Wang                    October, 2003               %
%                                                                                %   
%--------------------------------------------------------------------------------%

function [group,label,medoid]= K_Medoids(dist_matrix,k,num_iteration)

if (~(exist('num_iteration')))
   num_iteration = 200;
end

n=size(dist_matrix,1);
label=zeros(1,n);

medoid=ceil(rand(1,k)*n);    % inatialize the medoids (centers of clusters)

err=realmax;
no_change=0;

while no_change<num_iteration  % stop criterion

    new_medoid=[medoid(2:k),ceil(rand*n)];   % each time replace one medoid with a randomly chosen object
    sum_err=0;    %  this variable is used to record the distortion
    tmp_label=zeros(1,n);

    for i=1:n
        [M,I]=min(dist_matrix(i,new_medoid));
        tmp_label(i)=I;
        sum_err=sum_err+M;
    end

    if sum_err < err     % If the distortion is smallerm, the new medoid will be accepted.
        err = sum_err;
        medoid=new_medoid;
        label=tmp_label;
        no_change=0;
    else
        no_change=no_change+1;
    end
    
end


for i=1:k
    group{i}=[];
end

for i=1:n
    group{label(i)}=union(group{label(i)},i);
end



    
    





